#include <iostream>

using namespace std;

#define MAX_N 15

long long bases[] = {1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 3991680, 479001600, 6227020800, 87178291200, 1307674368000};

long long get_perm_order(int n, int data[])
{
	if (n == 1)
		return 0;
	long long r = (data[0] - 1) * bases[n-2];
	for (int i = 1; i < n; i++)
		if (data[i] > data[0])
			data[i]--;
	return r + get_perm_order(n-1, data+1);
}

void mth_perm(long long m, int n, int result[], int avail[])
{
	if (m == 0) {
		for (int i = 0; i < n; i++)
			result[i] = avail[i];
		return;
	}

	long long head = m / bases[n-2];
	result[0] = avail[head];

	for (int i = head; i < n; i++)
		avail[i] = avail[i+1];

	mth_perm(m - head * bases[n-2], n-1, result+1, avail);
}

int main()
{
	int x[] = {1, 5, 4, 2, 3};
	cout << get_perm_order(5, x) << endl;

	int y[5];
	for (int i = 1; i < bases[4]; i += 5) {
		int avail[] = {1, 2, 3, 4, 5};
		mth_perm(i, 5, y, avail);
		printf("[%3d]: ", i);
		for (int i = 0; i < 5; i++)
			printf("%d ", y[i]);
		printf("\n");
	}
}
